package swardToOffer.struct_5_stack_or_queue;


import java.util.Stack;

/**
 * @Author ChanZany
 * @Date 2021/5/25 19:05
 * @Version 1.0
 * 面试题52：两个链表的第一个公共结点
 * 题目：输入两个链表，找出它们的第一个公共结点。
 * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 * 方法1:两个辅助栈,分别对应两个链表,遍历压入栈,然后对应每个出栈的元素进行比较,当出栈的元素不相同时,该元素的前一个元素就是公共节点
 * [4,1,8,4,5]    8为公共节点
 * [5,0,1,8,4,5]
 * 方法2:双指针
 * 考虑构建两个节点指针 A​ , B 分别指向两链表头节点 headA , headB ，做如下操作：
 * 指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node(公共结点或null)时，共走步数为：
 *  a+(b-c) . 其中a为headA链表的长度,b为headB链表的长度,c为公共结点的长度.
 * 指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
 *  b+(a-c)
 * 此时,指针A,B重合,a+(b-c)=b+(a-c)
 * 当A,B有公共尾部时,A,B同时指向一个公共结点
 * 当A,B没有公共尾部时,A,B都指向null
 * 所以直接返回A或B即可
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class FirstCommonNodesInLists {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }


    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while (headA != null) {
            stack1.push(headA);
            headA = headA.next;
        }
        while (headB!=null){
            stack2.push(headB);
            headB = headB.next;
        }
        while (!stack1.isEmpty()&&!stack2.isEmpty()){
            ListNode nodeA = stack1.pop();
            ListNode nodeB = stack2.pop();
            if (nodeA!=nodeB) {
                return nodeA.next;
            }
            //这个条件需要加上,即当某个栈中以及弹出所有结点仍然没有找到不同的结点,则说明该栈的栈底结点(链表的头结点)就是公共结点
            if (stack1.isEmpty() || stack2.isEmpty())
                return nodeA;
        }
        return null;
    }

    public static void main(String[] args) {
        FirstCommonNodesInLists Main = new FirstCommonNodesInLists();
        ListNode headA = new ListNode(1);
        ListNode headB = new ListNode(2);
        headB.next = headA;
//        ListNode nodeA1 = new ListNode(2);
//        ListNode nodeA2 = new ListNode(3);
//        ListNode nodeComm = new ListNode(6);
//        ListNode nodeComm2 = new ListNode(7);
//
//        ListNode headB = new ListNode(4);
//        ListNode nodeB1 = new ListNode(5);
//        headA.next = nodeA1;
//        nodeA1.next = nodeA2;
//        nodeA2.next = nodeComm;
//        headB.next = nodeB1;
//        nodeB1.next = nodeComm;
//        nodeComm.next = nodeComm2;

        System.out.println(Main.getIntersectionNode(headA,headB)==null);
    }
}
